#!/usr/bin/perl
# vim: ts=4

use strict;
use warnings;
use constant GAP => -5;

our $score;

INIT {
  $score = {};
  my @th = split ' ', <DATA>;
  while (<DATA>) {
    my @tr = split;
    my $th = shift @tr;
    for my $i (0 .. $#tr) {
      $score->{$th}{$th[$i]} = $tr[$i];
    }
  }
}

chomp(my $s = <>);
chomp(my $t = <>);
my @s = split //, $s;
my @t = split //, $t;

my (@dp, @pre);
my @ans = (0, 0, 0);
$dp[0][0] = 0;
for my $i (0 .. @s) {
  for my $j (0 .. @t) {
    $dp[$i][$j] //= 0;
    if ($i > 0 && $dp[$i][$j] < $dp[$i - 1][$j] + GAP) {
      $dp[$i][$j] = $dp[$i - 1][$j] + GAP;
      $pre[$i][$j] = [$i - 1, $j];
    }
    if ($j > 0 && $dp[$i][$j] < $dp[$i][$j - 1] + GAP) {
      $dp[$i][$j] = $dp[$i][$j - 1] + GAP;
      $pre[$i][$j] = [$i, $j - 1];
    }
    if ($i > 0 && $j > 0) {
      my $tmp = $dp[$i - 1][$j - 1] + $score->{$s[$i - 1]}{$t[$j - 1]};
      if ($dp[$i][$j] < $tmp) {
        $dp[$i][$j] = $tmp;
        $pre[$i][$j] = [$i - 1, $j - 1];
      }
    }
    if ($ans[0] < $dp[$i][$j]) {
      @ans = ($dp[$i][$j], $i, $j);
    }
  }
}

($s, $t) = ('', '');
for (my ($i, $j) = @ans[1, 2]; $dp[$i][$j] > 0; ) {
  my ($ii, $jj) = @{$pre[$i][$j]};
  $s .= $s[$ii] if $ii < $i;
  $t .= $t[$jj] if $jj < $j;
  ($i, $j) = ($ii, $jj);
}
$ans[1] = reverse $s;
$ans[2] = reverse $t;
local $" = "\n";
print "@ans\n";

# http://rosalind.info/glossary/pam250/
__DATA__
   A  C  D  E  F  G  H  I  K  L  M  N  P  Q  R  S  T  V  W  Y
A  2 -2  0  0 -3  1 -1 -1 -1 -2 -1  0  1  0 -2  1  1  0 -6 -3
C -2 12 -5 -5 -4 -3 -3 -2 -5 -6 -5 -4 -3 -5 -4  0 -2 -2 -8  0
D  0 -5  4  3 -6  1  1 -2  0 -4 -3  2 -1  2 -1  0  0 -2 -7 -4
E  0 -5  3  4 -5  0  1 -2  0 -3 -2  1 -1  2 -1  0  0 -2 -7 -4
F -3 -4 -6 -5  9 -5 -2  1 -5  2  0 -3 -5 -5 -4 -3 -3 -1  0  7
G  1 -3  1  0 -5  5 -2 -3 -2 -4 -3  0  0 -1 -3  1  0 -1 -7 -5
H -1 -3  1  1 -2 -2  6 -2  0 -2 -2  2  0  3  2 -1 -1 -2 -3  0
I -1 -2 -2 -2  1 -3 -2  5 -2  2  2 -2 -2 -2 -2 -1  0  4 -5 -1
K -1 -5  0  0 -5 -2  0 -2  5 -3  0  1 -1  1  3  0  0 -2 -3 -4
L -2 -6 -4 -3  2 -4 -2  2 -3  6  4 -3 -3 -2 -3 -3 -2  2 -2 -1
M -1 -5 -3 -2  0 -3 -2  2  0  4  6 -2 -2 -1  0 -2 -1  2 -4 -2
N  0 -4  2  1 -3  0  2 -2  1 -3 -2  2  0  1  0  1  0 -2 -4 -2
P  1 -3 -1 -1 -5  0  0 -2 -1 -3 -2  0  6  0  0  1  0 -1 -6 -5
Q  0 -5  2  2 -5 -1  3 -2  1 -2 -1  1  0  4  1 -1 -1 -2 -5 -4
R -2 -4 -1 -1 -4 -3  2 -2  3 -3  0  0  0  1  6  0 -1 -2  2 -4
S  1  0  0  0 -3  1 -1 -1  0 -3 -2  1  1 -1  0  2  1 -1 -2 -3
T  1 -2  0  0 -3  0 -1  0  0 -2 -1  0  0 -1 -1  1  3  0 -5 -3
V  0 -2 -2 -2 -1 -1 -2  4 -2  2  2 -2 -1 -2 -2 -1  0  4 -6 -2
W -6 -8 -7 -7  0 -7 -3 -5 -3 -2 -4 -4 -6 -5  2 -2 -5 -6 17  0
Y -3  0 -4 -4  7 -5  0 -1 -4 -1 -2 -2 -5 -4 -4 -3 -3 -2  0 10
